Solving the Protein Threading Problem by Lagrangian Relaxation
Identifieur interne : 000D68 ( France/Analysis ); précédent : 000D67; suivant : 000D69Solving the Protein Threading Problem by Lagrangian Relaxation
Auteurs : Stefan Balev [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2004.
Abstract
Abstract: This paper presents an efficient algorithm for aligning aquery amino-acid sequence to a protein 3D structure template. Solving this problem is one of the main steps of the methods of protein structure prediction by threading. We propose an integer programming model and solve it by branch-and-bound algorithm. The bounds are computed using a Lagrangian dual of the model which turns out to be much easier to solve than its linear programming relaxation. The Lagrangian relaxations are computed using a dynamic programming algorithm. The experimental results show that our algorithm outperforms the commonly used methods. The proposed algorithm is general enough and can be easily plugged in most of the threading tools in order to increase their performance.
Url:
DOI: 10.1007/978-3-540-30219-3_16
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000D54
- to stream Istex, to step Curation: 000D54
- to stream Istex, to step Checkpoint: 000585
- to stream Main, to step Merge: 001375
- to stream Main, to step Curation: 001343
- to stream Main, to step Exploration: 001343
- to stream France, to step Extraction: 000D68
Links to Exploration step
ISTEX:161437BEB78DFE348CEFC8FFCEFB9D3E22379995Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct:series"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Solving the Protein Threading Problem by Lagrangian Relaxation</title><author><name sortKey="Balev, Stefan" sort="Balev, Stefan" uniqKey="Balev S" first="Stefan" last="Balev">Stefan Balev</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:161437BEB78DFE348CEFC8FFCEFB9D3E22379995</idno><date when="2004" year="2004">2004</date><idno type="doi">10.1007/978-3-540-30219-3_16</idno><idno type="url">https://api.istex.fr/document/161437BEB78DFE348CEFC8FFCEFB9D3E22379995/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000D54</idno><idno type="wicri:Area/Istex/Curation">000D54</idno><idno type="wicri:Area/Istex/Checkpoint">000585</idno><idno type="wicri:doubleKey">0302-9743:2004:Balev S:solving:the:protein</idno><idno type="wicri:Area/Main/Merge">001375</idno><idno type="wicri:Area/Main/Curation">001343</idno><idno type="wicri:Area/Main/Exploration">001343</idno><idno type="wicri:Area/France/Extraction">000D68</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Solving the Protein Threading Problem by Lagrangian Relaxation</title><author><name sortKey="Balev, Stefan" sort="Balev, Stefan" uniqKey="Balev S" first="Stefan" last="Balev">Stefan Balev</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire d’Informatique du Havre, Université du Havre, 25 rue Philippe Lebon, BP 540, 76058, Le Havre cedex</wicri:regionArea><placeName><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region><settlement type="city">Le Havre</settlement></placeName><orgName type="university">Université du Havre</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2004</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">161437BEB78DFE348CEFC8FFCEFB9D3E22379995</idno><idno type="DOI">10.1007/978-3-540-30219-3_16</idno><idno type="ChapterID">16</idno><idno type="ChapterID">Chap16</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: This paper presents an efficient algorithm for aligning aquery amino-acid sequence to a protein 3D structure template. Solving this problem is one of the main steps of the methods of protein structure prediction by threading. We propose an integer programming model and solve it by branch-and-bound algorithm. The bounds are computed using a Lagrangian dual of the model which turns out to be much easier to solve than its linear programming relaxation. The Lagrangian relaxations are computed using a dynamic programming algorithm. The experimental results show that our algorithm outperforms the commonly used methods. The proposed algorithm is general enough and can be easily plugged in most of the threading tools in order to increase their performance.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Haute-Normandie</li><li>Région Normandie</li></region><settlement><li>Le Havre</li></settlement><orgName><li>Université du Havre</li></orgName></list><tree><country name="France"><region name="Région Normandie"><name sortKey="Balev, Stefan" sort="Balev, Stefan" uniqKey="Balev S" first="Stefan" last="Balev">Stefan Balev</name></region><name sortKey="Balev, Stefan" sort="Balev, Stefan" uniqKey="Balev S" first="Stefan" last="Balev">Stefan Balev</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/France/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000D68 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000D68 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/France
|area= LeHavreV1
|flux= France
|étape= Analysis
|type= RBID
|clé= ISTEX:161437BEB78DFE348CEFC8FFCEFB9D3E22379995
|texte= Solving the Protein Threading Problem by Lagrangian Relaxation
}}
| This area was generated with Dilib version V0.6.25. |  |